This invention relates in general to a methodology for optimizing the allocation of free memory blocks using link lists and, more particularly, to a method and implementation of a dual link list structure for free memory.
Conventional link lists methods of data storage for shared memory, i.e., volatile or random access memory (RAM), require that the link list be read every time a block of memory needs to be allocated. These methods typically determine a free list, a link list defining a block of available memory, when the head-tail pointer is established and when a block of memory needs to be allocated. Allocation of memory using this process takes longer than the time available in some pipelined architectures.
Another method to process memory allocation is described in U.S. Pat. No. 6,049,802 to Waggener and Bray entitled “System And Method For Generating A Linked List In A Computer Memory”. This patent discloses link lists that contain several key list parameters. A memory manager determines to which link list the data belongs based on key list parameters. This patent also discloses that the address of the next location in the link list is determined before data is written to the current location. While this allows the next address to be written in the same cycle in which data is written, the free list scheme disclosed does not address optimization for the allocation and management of free memory blocks. The method of the '802 patent appends and maintains a single free list.
One more memory storage technique is described in U.S. Pat. No. 5,303,302 issued to Burrows entitled “Network Packet Receiver With Buffer Logic For Reassembling Interleaved Data Packets”. In this patent, a network controller receives encrypted data packets. A packet directory has an entry for each data packet stored in a buffer. Each directory entry contains a pointer to the first and last location in the buffer where a corresponding data packet is stored along with status information for the data packet. A method is also disclosed for partial data packet transmission management for the prevention of buffer overflow. Processing optimization for the allocation and management of free memory blocks is not achieved in this method.
In addition, neither of the above patents addresses the issue of an allocation and a free list occurring concurrently. In that case, extra memory bandwidth is required to both do the allocation step of reading from the free list and then splicing onto the free list.